#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100
#define INF 99999

// 修正数据结构定义中的中文分号和方括号
typedef struct message {
    int num;           // 景点代码
    char name[100];    // 景点名称
    char pro[500];     // 简介
} Ciceroni;

// 图的邻接矩阵表示
typedef struct {
    Ciceroni vexs[MAX];  // 顶点表
    int arcs[MAX][MAX];  // 邻接矩阵
    int vexnum, arcnum;           // 图的当前顶点数和边数
} MGraph;

// 景点信息初始化（修正字符串格式和逗号分隔）
Ciceroni school[10] = {
    {1, "芭蕉食堂", "周围都有芭蕉的食堂"},
    {2, "山谷运动场", "350米操场"},
    {3, "校医务所安全保障处", "保障学生的安全"},
    {4, "长芗食堂", "在教学楼下的食堂"},
    {5, "体育场", "400米标准场"},
    {6, "香樟食堂", "距离图书馆最近的食堂"},
    {7, "礼堂", "大礼堂"},
    {8, "实验剧场", "剧场社团"},
    {9, "美术馆", "学生艺术展"},
    {10, "图书馆 ""学校最美的地方"}
};

// 初始化图
void InitGraph(MGraph *G) {
    G->vexnum = 10;  // 默认10个景点
    G->arcnum = 0;
    
    // 初始化顶点信息
    for (int i = 0; i < G->vexnum; i++) {
        G->vexs[i] = school[i];
    }
    
    // 初始化邻接矩阵，所有路径赋最大值
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            if (i == j)
                G->arcs[i][j] = 0;  // 自己到自己的距离为0
            else
                G->arcs[i][j] = INF;  // 初始化为无穷大
        }
    }
}

// 添加边（路径）
void AddArc(MGraph *G, int v1, int v2, int weight) {
    if (v1 < 0 || v1 >= G->vexnum || v2 < 0 || v2 >= G->vexnum) {
       
        return;
    }
    
    // 无向图，对称赋值
    G->arcs[v1][v2] = weight;
    G->arcs[v2][v1] = weight;
    G->arcnum++;
}

// Dijkstra算法求最短路径
void Dijkstra(MGraph *G, int v0, int dist[], int path[]) {
    int n = G->vexnum;
    int s[MAX];  // 标记顶点是否已找到最短路径
    
    // 初始化
    for (int v = 0; v < n; v++) {
        s[v] = 0;
        dist[v] = G->arcs[v0][v];
        if (dist[v] < INF && v != v0)
            path[v] = v0;
        else
            path[v] = -1;
    }
    
    s[v0] = 1;  // 源点v0已找到最短路径
    
    // 主循环
    for (int i = 1; i < n; i++) {
        int min = INF;
        int u = v0;
        
        // 选择距离最小的顶点u
        for (int v = 0; v < n; v++) {
            if (!s[v] && dist[v] < min) {
                u = v;
                min = dist[v];
            }
        }
        
        s[u] = 1;  // 顶点u已找到最短路径
        
        // 更新剩余顶点的距离
        for (int v = 0; v < n; v++) {
            if (!s[v] && G->arcs[u][v] < INF && dist[u] + G->arcs[u][v] < dist[v]) {
                dist[v] = dist[u] + G->arcs[u][v];
                path[v] = u;
            }
        }
    }
}

// 输出最短路径
void PrintPath(MGraph *G, int path[], int v, int v0) {
    if (path[v] == -1) {
        printf("%s", G->vexs[v].name);
        return;
    }
    
    PrintPath(G, path, path[v], v0);
    printf(" -> %s", G->vexs[v].name);
}

// 输出最短路径和最短距离
void ShortestPath(MGraph *G, int v1, int v2) {
    int dist[MAX], path[MAX];
    Dijkstra(G, v1, dist, path);
    
    if (dist[v2] == INF) {
        printf("景点 %d 到景点 %d 没有路径！\n", v1+1, v2+1);
    } else {
        printf("从 %s 到 %s 的最短路径为：\n", G->vexs[v1].name, G->vexs[v2].name);
        PrintPath(G, path, v2, v1);
        printf("\n最短距离为：%d\n", dist[v2]);
    }
}

// 输入景点代码查景点名称和简介
void QueryVexInfo(MGraph *G, int num) {
    if (num < 1 || num > G->vexnum) {
        printf("景点编号不存在！\n");
        return;
    }
    
    Ciceroni vex = G->vexs[num-1];
    printf("景点编号：%d\n", vex.num);
    printf("景点名称：%s\n", vex.name);
    printf("景点简介：%s\n", vex.pro);
}

// 输入景点代码查到其它景点的最短距离
void QueryAllShortestPaths(MGraph *G, int num) {
    if (num < 1 || num > G->vexnum) {
        printf("景点编号不存在！\n");
        return;
    }
    
    int dist[MAX], path[MAX];
    Dijkstra(G, num-1, dist, path);
    
    printf("从 %s 到其他景点的最短距离为：\n", G->vexs[num-1].name);
    for (int i = 0; i < G->vexnum; i++) {
        if (i != num-1) {
            if (dist[i] == INF) {
                printf("到 %s：无路径\n", G->vexs[i].name);
            } else {
                printf("到 %s：%d\n", G->vexs[i].name, dist[i]);
            }
        }
    }
}

// 查找所有路径的辅助函数
void FindAllPathsUtil(MGraph *G, int u, int d, int visited[], int path[], int *path_index) {
    // 标记当前节点为已访问，并加入路径
    visited[u] = 1;
    path[(*path_index)++] = u;
    
    // 如果到达目标节点，则打印路径
    if (u == d) {
        for (int i = 0; i < *path_index; i++)
            printf("%s ", G->vexs[path[i]].name);
        printf("\n");
    } else {
        // 递归访问所有邻接节点
        for (int i = 0; i < G->vexnum; i++) {
            if (G->arcs[u][i] < INF && !visited[i])
                FindAllPathsUtil(G, i, d, visited, path, path_index);
        }
    }
    
    // 回溯：移除当前节点并标记为未访问
    (*path_index)--;
    visited[u] = 0;
}

// 查找所有路径
void FindAllPaths(MGraph *G, int v1, int v2) {
    int visited[MAX] = {0};
    int path[MAX];
    int path_index = 0;
    
    printf("从 %s 到 %s 的所有路径为：\n", G->vexs[v1].name, G->vexs[v2].name);
    FindAllPathsUtil(G, v1, v2, visited, path, &path_index);
}

// 增加景点
void AddVex(MGraph *G, Ciceroni vex) {
    if (G->vexnum >= MAX) {
        printf("景点数量已达上限！\n");
        return;
    }
    
    G->vexs[G->vexnum] = vex;
    
    // 初始化新顶点的邻接矩阵
    for (int i = 0; i <= G->vexnum; i++) {
        G->arcs[G->vexnum][i] = INF;
        G->arcs[i][G->vexnum] = INF;
    }
    G->arcs[G->vexnum][G->vexnum] = 0;
    
    G->vexnum++;
    printf("成功添加景点：%s\n", vex.name);
}

// 删除景点
void DeleteVex(MGraph *G, int num) {
    if (num < 1 || num > G->vexnum) {
        printf("景点编号不存在！\n");
        return;
    }
    
    int index = num - 1;
    
    // 删除顶点相关的边
    for (int i = 0; i < G->vexnum; i++) {
        if (G->arcs[index][i] < INF)
            G->arcnum--;
        G->arcs[index][i] = INF;
        G->arcs[i][index] = INF;
    }
    
    // 移动后面的顶点填补空缺
    for (int i = index; i < G->vexnum - 1; i++) {
        G->vexs[i] = G->vexs[i + 1];
        
        // 更新邻接矩阵
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = G->arcs[i + 1][j];
            G->arcs[j][i] = G->arcs[j][i + 1];
        }
    }
    
    G->vexnum--;
    printf("成功删除景点！\n");
}

// 更新景点信息
void UpdateVexInfo(MGraph *G, int num, Ciceroni newVex) {
    if (num < 1 || num > G->vexnum) {
        printf("景点编号不存在！\n");
        return;
    }
    
    G->vexs[num-1] = newVex;
    printf("成功更新景点信息！\n");
}

// 更新路径信息
void UpdateArc(MGraph *G, int v1, int v2, int weight) {
    if (v1 < 0 || v1 >= G->vexnum || v2 < 0 || v2 >= G->vexnum) {
        printf("景点编号无效！\n");
        return;
    }
    
    if (G->arcs[v1][v2] < INF) {
        G->arcs[v1][v2] = weight;
        G->arcs[v2][v1] = weight;
        printf("成功更新路径信息！\n");
    } else {
        printf("路径不存在，无法更新！\n");
    }
}

// 显示菜单
void ShowMenu() {
    printf("\n========== 校园导游系统 ==========\n");
    printf("1. 查询景点信息\n");
    printf("2. 查询两景点间最短路径\n");
    printf("3. 查询两景点间所有路径\n");
    printf("4. 查询到其他景点的最短距离\n");
    printf("5. 添加景点\n");
    printf("6. 删除景点\n");
    printf("7. 更新景点信息\n");
    printf("8. 更新路径信息\n");
    printf("0. 退出系统\n");
    printf("=================================\n");
    printf("请输入您的选择：");
}

int main() {
    MGraph G;
    InitGraph(&G);
    
    // 初始化一些路径（示例数据）
    AddArc(&G, 1, 2, 200);  // 芭蕉食堂到山谷运动场 
    AddArc(&G, 2, 3, 500);  // 山谷运动场到长芗食堂
    AddArc(&G, 2, 4, 100);  // 山谷运动场到校医务所安全保障体处 
    AddArc(&G, 3, 4, 200);  // 长芗食堂到医务所安全保障体处
    AddArc(&G, 3, 5, 550);  //  长芗食堂到体育场 
    AddArc(&G, 5, 6, 250);  //  体育场到香樟食堂 
    AddArc(&G, 6, 7, 300);  // 香樟食堂到礼堂 
    AddArc(&G, 7, 8, 300);  // 礼堂到实验剧场 
    AddArc(&G, 7, 10, 140);  // 礼堂到图书馆 
    AddArc(&G, 8, 9, 50);  // 实验剧场到美术管 
     AddArc(&G, 9, 10, 50);//美术观到图书馆 
    
    int choice, num, v1, v2, weight;
    Ciceroni vex;
    
    do {
        ShowMenu();
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("请输入景点编号：");
                scanf("%d", &num);
                QueryVexInfo(&G, num);
                break;
            case 2:
                printf("请输入起点和终点景点编号：");
                scanf("%d %d", &v1, &v2);
                ShortestPath(&G, v1-1, v2-1);
                break;
            case 3:
                printf("请输入起点和终点景点编号：");
                scanf("%d %d", &v1, &v2);
                FindAllPaths(&G, v1-1, v2-1);
                break;
            case 4:
                printf("请输入景点编号：");
                scanf("%d", &num);
                QueryAllShortestPaths(&G, num);
                break;
            case 5:
                printf("请输入景点编号：");
                scanf("%d", &vex.num);
                printf("请输入景点名称：");
                scanf("%s", vex.name);
                printf("请输入景点简介：");
                scanf("%s", vex.pro);
                AddVex(&G, vex);
                break;
            case 6:
                printf("请输入要删除的景点编号：");
                scanf("%d", &num);
                DeleteVex(&G, num);
                break;
            case 7:
                printf("请输入要更新的景点编号：");
                scanf("%d", &num);
                printf("请输入新的景点信息：\n");
                printf("编号：");
                scanf("%d", &vex.num);
                printf("名称：");
                scanf("%s", vex.name);
                printf("简介：");
                scanf("%s", vex.pro);
                UpdateVexInfo(&G, num, vex);
                break;
            case 8:
                printf("请输入起点和终点景点编号及新的路径长度：");
                scanf("%d %d %d", &v1, &v2, &weight);
                UpdateArc(&G, v1-1, v2-1, weight);
                break;
            case 0:
                printf("感谢使用校园导游系统，再见！\n");
                break;
            default:
                printf("无效的选择，请重新输入！\n");
        }
    } while (choice != 0);
    
    return 0;
}